Strobogrammatic number II

Time: O(N2x5(N/2)); Space: O(N); medium

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Find all strobogrammatic numbers that are of length = n.

Example 1:

Input: n = 2

Output: [“11”,“69”,“88”,“96”]

Example 2:

Input: n = 1

Output: [“0”,“1”,“8”]

[3]:

class Solution1(object):
    """
    Time: O(N^2x5^(N/2))
    Space: O(N)
    """
    lookup = {'0':'0',
              '1':'1',
              '6':'9',
              '8':'8',
              '9':'6'}

    def findStrobogrammatic(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        return self.findStrobogrammaticRecu(n, n)

    def findStrobogrammaticRecu(self, n, k):
        if k == 0:
            return ['']
        elif k == 1:
            return ['0', '1', '8']

        result = []
        for num in self.findStrobogrammaticRecu(n, k - 2):
            for key, val in self.lookup.items():
                if n != k or key != '0':
                    result.append(key + num + val)

        return result

[4]:

s = Solution1()

n = 2
assert s.findStrobogrammatic(n) == ["11","69","88","96"]

n = 1
assert s.findStrobogrammatic(n) == ["0","1","8"]